<head>
    <meta charset="UTF-8">
<title>算法训练 Password Suspects</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p class="MsoNormal"><span lang="EN-US">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">你是一个秘密犯罪组织</span><span lang="EN-US">the Sneaky Underground Smug Perpetrators of Evil Crimes and Thefts(SUSPECT)</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">里的电脑高手。</span><span lang="EN-US">SUSPECT</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">最新的邪恶犯罪目标是他们最大的对手</span><span lang="EN-US">the Indescribably Clever Policemen&rsquo;s Club</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">（</span><span lang="EN-US">ICPC</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">），一切都已经准备就绪，除了一件小事：</span><span lang="EN-US">ICPC</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin">的主机密码。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">密码仅有小写字母</span><span lang="EN-US">&rsquo;a&rsquo;-&lsquo;z&rsquo;</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">构成。此外，通过各种偷窥，你已经确定了密码的长度，和一些（可能重叠）密码中的子串，尽管你不清楚他们出现在密码的哪个位置。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">例如，你知道密码的长度是</span><span lang="EN-US">10</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">个字符且你观察到了子串&ldquo;</span><span lang="EN-US">hello</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">&rdquo;和&ldquo;</span><span lang="EN-US">world</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">&rdquo;。那么密码一定是&ldquo;</span><span lang="EN-US">helloworld</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">&rdquo;或者&ldquo;</span><span lang="EN-US">worldhello</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">&rdquo;。</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">&nbsp; &nbsp; 问题在于这些信息是否能将密码的可能数缩减到一个合理的范围内。要回答这个问题，你的任务是写一个程序判断可能的密码的总数目，如果可能的密码数目不超过</span><span lang="EN-US">42</span><span style="font-family: 宋体;">，打印出所有可能密码。</span></p>
<p>【输入格式】</p>
<p class="MsoNormal"><span lang="EN-US">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">第一行包含两个整数</span><span lang="EN-US">N</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">和</span><span lang="EN-US">M</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">，分别表示密码的长度和已知的密码中子串的数量。接下来</span><span lang="EN-US">M</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin">行，每行一个密码中的已知子串。</span><span lang="EN-US"><o:p></o:p></span></p>
<p>【输出格式】</p>
<p class="MsoNormal"><span lang="EN-US">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">第一行输出</span><span lang="EN-US">Y</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin">，</span><span lang="EN-US">Y</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin">表示可能的密码的数目。如果</span><span lang="EN-US">Y</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin">不超过</span><span lang="EN-US">42</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin">，接下来按照字典序，每行一个密码，依次输出所有可能的密码。</span></p>
<p class="MsoNormal">【样例输入】</p>
<div>
<div>10 2&nbsp;</div>
<div>hello&nbsp;</div>
<div>world&nbsp;</div>
</div>
<p>【样例输出】</p>
<div>2</div>
<div>
<div>helloworld&nbsp;</div>
<div>worldhello</div>
</div>
<p class="MsoNormal"><span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal">【样例输入】</p>
<div>10 0</div>
<p>【样例输出】</p>
<div>141167095653376</div>
<div>【样例输入】<br />
<div>4 1&nbsp;</div>
<div>icpc</div>
【样例输出】<br />
<div>1</div>
<div>icpc</div>
</div>
<p>【数据规模和约定】</p>
<p class="MsoNormal"><span lang="EN-US">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1&lt;=N&lt;=25</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">，</span><span lang="EN-US">0&lt;=M&lt;=10</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">，子串长度</span><span lang="EN-US">&lt;=10</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">，所有字符均为小写字母</span><span lang="EN-US">&rsquo;a&rsquo;-&lsquo;z&rsquo;</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">，输入数据保证答案不超过</span><span lang="EN-US">10^15</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin">。</span><span lang="EN-US"><o:p></o:p></span></p>